package main

import (
	"fmt"
	"sort"
)

// 第350题：两个数组的交集
// 给定两个数组，编写一个函数来计算它们的交集。

func intersect(nums1 []int, nums2 []int) []int {
	if len(nums1) > len(nums2) {
		return intersect(nums2, nums1)
	}
	ret := []int{}
	//m := map[int]int{}
	var m = map[int]int{}

	// 1. 记录数组1,每个元素出现的次数
	for _, num := range nums1 {
		m[num]++
	}
	// 2. 让数组2去跟数组1对比,如果数组2的某个数在数组1中有那么这个数就是交集的一部分,否则就不是
	for _, num := range nums2 {
		// 如果数组1有num那么这个num就是交集
		if m[num] > 0 {
			ret = append(ret, num)
			m[num]--
		}
	}
	return ret
}

// 双指针法
func intersect2(nums1 []int, nums2 []int) []int {
	var i, j, k = 0, 0, 0
	sort.Ints(nums1)
	sort.Ints(nums2)
	for i < len(nums1) && j < len(nums2) {
		if nums1[i] == nums2[j] {
			nums1[k] = nums1[i]
			i++
			j++
			k++
		} else if nums1[i] < nums2[j] {
			i++
		} else {
			j++
		}
	}
	return nums1[:k]
}

func main() {
	nums1 := []int{1, 2, 2, 1}
	nums2 := []int{2, 2}
	//fmt.Println(intersect(nums1, nums2))
	fmt.Println(intersect2(nums1, nums2))
}
